1. Field of the Invention
This invention relates to the field of integrated circuit design, and in particular to programmable gate arrays.
2. Description of the Related Art
Gate array integrated circuits are common in the art, and allow for the design of application specific integrated circuits via an interconnection among predefined and prefabricated gate array cells. Field Programmable Gate Array (FPGA) allow for the creation, or programming, of the interconnection among the cells at a user's site, using commonly available programming devices. The interconnections may be created by fusing links, by enabling selected switches, by storing a pattern that controls available switches, and so on. U.S. Pat. No. 5,594,363, "Logic Cell and Routing Architecture in a Field Programmable Gate Array, filed Jan. 14, 1997 for Freeman et al, incorporated by reference herein, discloses a technique for routing among cells that includes switch matrices that connect select vertical wires to horizontal wires, based on the contents of a nonvolatile memory cell. Typically, a designer provides a description of the function to be performed, and a computer-aided-design (CAD) program determines the interconnect programming required to effect that function. The description may be a logic diagram, a data flow diagram, a state diagram or table, a sequence of instructions in a structured design language, and so on.
The conversion from a description of the design to the programming of a gate array is dependent upon the contents of the gate array. If the cells of the gate array are high level blocks, such as counters, parity generators, and the like, then the amount of programming required is limited to the interconnections among these large, or coarse-grain, cells. If, on the other hand, the cells of the gate array are low level blocks, such as gates, latches, and the like, then the amount of programming is significantly higher, because these smaller, or fine-grain, cells need to be interconnected to effect the higher level functions, such as the aforementioned counters and parity generators. In some designs, higher circuit densities can be achieved via the use of fine-grain cells, because simpler functions can be implemented with a small low-level cell, rather than with a larger high-level cell whose higher level functions go unused. Conversely, some complex designs cannot be efficiently embodied in a fine-grain gate array, because the amount of interconnection required among the low-level cells exceed the capacity of the gate array. In some cases, the interconnections may be within the capacity of the gate array, but the resultant routing paths among the low-level cells exceed the propagation delay or skew limits required to effect the intended function. For optimal performance, the fine-grained cells that are related to a particular function should be co-located, but this often places constraints on the routing for connections among functional blocks when such co-locations create routing "bottlenecks".
Various architectures have been proposed to optimize the tradeoffs among circuit density, routing efficiency, performance limits, and the like. U.S. Pat. No. 5,001,368, "Configurable Logic Array", issued Mar. 19, 1991 to Cliff et al, for example, notes the deficiencies of a gate array architecture that only includes NAND gate cells, and specifies the inclusion of additional circuitry to include a latch function in each cell. The need for a latch function is a common theme in conventional gate array cell design, because if the devices that form the latch are interconnected via long routing paths, or via intermediate buffers, the phase shift that is introduced could cause the latch to oscillate. Typical gate array cells commonly include at least one latch, sometimes more. U.S. Pat. No. 5,055,718, "Logic Module with Configurable Combinational and Sequential Blocks", issued Oct. 8, 1991 to Galbraith et al, specifies a configurable gate array cell that can effect "a wide variety" of combinational and sequential logic functions, ranging from a simple NAND function to an edge-triggered flip-flop with asynchronous reset. As noted above, however, the same amount of cell area is consumed regardless of whether a simple NAND gate or complex flip-flop is being implemented.
To ease the routing task, U.S. Pat. No. 5,831,448, "Function Unit for Fine-Grained FPGA", issued Nov. 3, 1998 to Kean et al, specifies the organization of configurable gate array cells into a hierarchy of blocks, such as a 4.times.4 cell block, a 4.times.4 organization of the 4.times.4 cell block, and so on. Each level of the hierarchy includes a routing path specific to that level, thereby allowing for a routing strategy that is logarithmic in terms of distance. The aforementioned U.S. Pat. No. 5,594,363 also discloses the use of hierarchical routing channels. The Motorola MPA 1000 family of commercially available FPGAs provides multi-functioned configurable gate array cells that are organized in zones of 10.times.10 cells and ancillary components, such as port cells and clock distribution cells, the zones being organized into 4 quadrants. A hierarchy of routing paths are provided: a local interconnect provides the connection among adjacent and near-adjacent cells; a medium interconnect provides the interconnection among zones; and a global interconnect provides the interconnection among quadrants, as well as global signal and bus routing.
Although hierarchical routing is effective for managing interconnection complexities, a fixed hierarchy of cells can lead to inefficiencies when the cell hierarchy does not conform to the hierarchy of functions used in the design. Similarly, although multi-functioned configurable cells ease the routing task by containing medium-complexity devices such as flip-flops, the achievable circuit density is directly affected by the number of low-level functions in the design, because regardless of simplicity, they will each consume a medium-complexity, medium-sized cell. Additionally, the partitioning of the area into zones of logic elements and zones of routing paths can also lead to inefficiencies when available logic elements are made unaccessible due to a commitment of all available routing paths to other logic elements, or preferred routing paths are made unaccessible to particular logic elements.